import java.util.HashMap;
import java.util.Map;

public class Leetcode {
}

//leetcode:6:Z字形变换
class Solution1 {
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        int n = s.length();
        //计算公差
        int d = 2*numRows-2;
        StringBuilder ret = new StringBuilder();
        //将第一行的数据添加到字符串中
        for(int i = 0;i < n;i+=d){
            ret.append(s.charAt(i));
        }
        //将中间的数据添加到字符串中
        for(int k = 1;k < numRows-1;k++){
            //是第几行就从第几个数开始，每次存入两个数据，第2个数据于第4个数据相差d-k
            for(int i = k,j = d-k;i < n ||j < n;i+=d,j+=d){
                if(i < n)ret.append(s.charAt(i));
                if(j < n)ret.append(s.charAt(j));
            }
        }
        //将最后一行数据添加到字符串中
        for(int i = numRows-1;i < n;i+=d){
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }
}
//leetcode:38:外观数组
class Solution2 {
    public String countAndSay(int n) {
        String s = "1";//字符串从1开始
        for(int i = 1; i < n;i++){
            StringBuilder ret = new StringBuilder();
            int len = s.length();
            //利用双指针从0开始变量
            for(int left = 0,right = 0;right < len ; ){
                //遇到相同的字符right++
                while(right < len && s.charAt(left) == s.charAt(right)){
                    right++;
                }
                //添加元素的个数和这个元素
                ret.append(Integer.toString(right-left));
                ret.append(s.charAt(left));
                left = right;
            }
            s = ret.toString();
        }
        return s;
    }
}

//leetcode:1419：数青蛙
class Solution3 {
    public int minNumberOfFrogs(String croakOfFrogs) {
        //转换成字符数组
        char[] croak = croakOfFrogs.toCharArray();
        //将蛙声设置位字符串
        String s = "croak";
        int n = s.length();
        int[] hash = new int[n];
        //根据哈希表依次存入字符，确定每个字符在哈希数组中对应的位置
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0;i < n;i++){
            map.put(s.charAt(i),i);
        }

        //遍历字符数组
        for(char ch : croak){
            //如果字符等于‘c‘
            if(ch == s.charAt(0)){
                //如果此时字符为’c‘,并且k位置的值大于0
                if(hash[n-1] > 0){
                    //k的值就减一
                    hash[n-1]--;
                }
                //c的值加一
                hash[0]++;
            }else{//如果遇到的字符不是’c‘
                //在哈希表中找到这个字符对应在哈希数组中的位置
                int index = map.get(ch);
                //如果这个字符前一个字符为0，代表这个字符串不能形成蛙声，返回-1
                if(hash[index-1] == 0){
                    return -1;
                }
                //如果不为0，就让前一个字符的个数减一，同时让此时的字符加一
                hash[index-1]--;
                hash[index]++;
            }
        }
        //最后遍历除最后一位（k）的哈希数组
        for(int i = 0;i < n-1;i++){
            //如果除k位置以外还存在字符就代表不能形成蛙声返回-1
            if(hash[i] != 0){
                return -1;
            }
        }
        //最后如果除k位置外都为0，就代表能形成蛙声，返回此时k位置的个数
        return hash[n-1];
    }
}





//leetcode:53：最大子数组之和
class Solution4 {
    public int maxSubArray(int[] nums) {
        int ans = nums[0],sum = nums[0];
        int left = 0,right = 0;
        for(right = 1; right < nums.length;right++){
            while(sum <= 0 && left < right){
                sum -= nums[left];
                left++;
            }
            sum += nums[right];
            ans = Math.max(ans,sum);
        }
        return ans;
    }
}